package com.code.leetcode.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/2 11:36
 */
public class The38 {
    Set<String> set = new HashSet<>();
    String s;
    boolean[] visited;

    public String[] permutation(String s) {
        if (s == null) return new String[]{};
        this.s = s;
        visited = new boolean[s.length()];

        dfs("");

        return set.toArray(new String[0]);
    }

    public void dfs(String p) {
        if (p.length() == s.length()) {
            set.add(p);
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (visited[i]) continue;
            visited[i] = true;
            dfs(p + String.valueOf(c));
            visited[i] = false;
        }

    }
}
